//class Solution
//{
//public:
//	string convert(string s, int numRows)
//	{
//		if (numRows == 1) return s;
//
//		string ret;
//		int d = 2 * numRows - 2, n = s.size();
//
//		for (int i = 0; i < n; i += d)
//			ret += s[i];
//
//		for (int k = 1; k < numRows - 1; k++) 
//		{
//			for (int i = k, j = d - k; i < n || j < n; i += d, j += d)
//			{
//				if (i < n) ret += s[i];
//				if (j < n) ret += s[j];
//			}
//		}
//
//		for (int i = numRows - 1; i < n; i += d)
//			ret += s[i];
//		return ret;
//	}
//};






//class Solution
//{
//public:
//	string countAndSay(int n)
//	{
//		string ret = "1";
//		for (int i = 1; i < n; i++)
//		{
//			string tmp;
//			int len = ret.size();
//			for (int left = 0, right = 0; right < len; )
//			{
//				while (right < len && ret[left] == ret[right]) right++;
//				tmp += to_string(right - left) + ret[left];
//				left = right;
//			}
//			ret = tmp;
//		}
//		return ret;
//	}
//};






//class Solution
//{
//public:
//	void sortColors(vector<int>& nums)
//	{
//		int n = nums.size();
//		int left = -1, right = n, i = 0;
//		while (i < right)
//		{
//			if (nums[i] == 0) swap(nums[++left], nums[i++]);
//			else if (nums[i] == 1) i++;
//			else swap(nums[--right], nums[i]);
//		}
//	}
//};




class Solution
{
public:
	vector<int> sortArray(vector<int>& nums)
	{
		srand(time(NULL)); 
		qsort(nums, 0, nums.size() - 1);
		return nums;
	}
	void qsort(vector<int>& nums, int l, int r)
	{
		if (l >= r) return;
		int key = getRandom(nums, l, r);
		int i = l, left = l - 1, right = r + 1;
		while (i < right)
		{
			if (nums[i] < key) swap(nums[++left], nums[i++]);
			else if (nums[i] == key) i++;
			else swap(nums[--right], nums[i]);
		}
		qsort(nums, l, left);
		qsort(nums, right, r);
	}
	int getRandom(vector<int>& nums, int left, int right)
	{
		int r = rand();
		return nums[r % (right - left + 1) + left];
	}
};